import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0)
            return res;
        HashMap<String, Integer> wordTable = new HashMap<>();
        int step = words[0].length();
        for (String word : words) {
            wordTable.put(word, wordTable.getOrDefault(word, 0) + 1);
        }

        for (int i = 0; i < step; i++) {
            HashMap<String, Integer> subTable = new HashMap<>();
            //start：窗口起始下标，end:窗口结束下标，count：窗口中单词个数
            int start = i, end = i, count = 0;
            while (end + step <= s.length()) {
                String word = s.substring(end, end + step);
                if (wordTable.containsKey(word)) {
                    int numInSub = subTable.getOrDefault(word, 0) + 1;
                    subTable.put(word, numInSub);
                    int numInWords = wordTable.get(word);
                    count++;
                    end += step;
                    //如果word在子串中的个数超出规定个数，窗口右移
                    while (numInSub > numInWords) {
                        String firstWord = s.substring(start, start + step);
                        int firstNum = subTable.getOrDefault(firstWord, 0) - 1;
                        subTable.put(firstWord, firstNum);
                        count--;
                        start += step;
                        if (firstWord.equals(word)) {
                            numInSub--;
                        }
                    }
                } else {
                    subTable.clear();
                    count = 0;
                    end += step;
                    start = end;
                }
                if (count == words.length) {
                    res.add(start);
                }
            }
        }

        return res;
    }
}
